package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-17 17:22
 **/
public class LeetCode19 {
    /**
     * 自己写的两边遍历解法
     * @param head
     * @param n
     * @return
     */
    /*public ListNode removeNthFromEnd(ListNode head, int n) {
        int count = 0;
        //伪头结点
        ListNode tou = new ListNode(0,head);
        ListNode temp = tou;
        //计算链表的长度
        while (temp.next != null) {
            count++;
            temp = temp.next;
        }
        temp = tou;
        int no = count - n;
        for (int i = 0; i < no; i++) {
            temp = temp.next;
        }
        temp.next = temp.next.next;
        return tou.next;
    }*/

    /**
     * 巧妙地双指针解法
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //伪头结点
        ListNode tou = new ListNode(0,head);
        //指针1
        ListNode first = head;
        //指针2
        ListNode second = tou;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        while (first != null) {
            second = second.next;
            first = first.next;
        }
        second.next = second.next.next;
        return tou.next;
    }
}
